// Package day_02_mid_sort merge_sort
// @Title day_02_mid_sort
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/8/30 17:17
// @Create  2021/8/30 17:17
package day_02_mid_sort

import "fmt"

func merge(arr []int, L, M, R int) {
	help := make([]int, R-L+1)
	i := 0
	p1 := L
	p2 := M + 1
	for p1 <= M && p2 <= R {
		if arr[p1] <= arr[p2] {
			help[i] = arr[p1]
			p1++
		} else {
			help[i] = arr[p2]
			p2++
		}
		i++
	}
	for p1 <= M {
		help[i] = arr[p1]
		i++
		p1++
	}
	for p2 <= R {
		help[i] = arr[p2]
		i++
		p2++
	}
	for j := 0; j < len(help); j++ {
		arr[L+j] = help[i]
	}
}

func process(arr []int, L, R int) []int {
	mid := L + (R-L)>>1
	if L < R {
		process(arr, L, mid)
		process(arr, mid+1, R)
	}
	merge(arr, L, mid, R)
	return arr
}

// MergeSort 归并排序
func MergeSort(nums []int) []int {
	if nums == nil || len(nums) < 2 {
		return nums
	}
	res := process(nums, 0, len(nums)-1)
	fmt.Println(res)
	return nums
}
